package com.shr.code_interview;

public class Solution_7 {
	
	public static TreeNode reConstructBinaryTree(int [] pre,int [] in) {
		return reConstruct(pre,in,0,pre.length-1,0,in.length-1) ;
	    
	}
	
	private static TreeNode reConstruct(int[] pre, int [] in, int preStart, int preEnd, int inStart, int inEnd)
	{
		TreeNode root = new TreeNode(pre[preStart]);
		root.left = null ;
		root.right = null ;
		
		if(preEnd - preStart == 0 && inEnd - inStart == 0)
			return root ;
		int rootIndex = 0;
		for(int i = inStart; i<= inEnd; i++){
			if(in[i] == pre[preStart]){
				rootIndex = i ;
				break ;
			}
				
		}
		int inLeftTreeEnd = rootIndex - 1;
		int inRightTreeStart = rootIndex + 1 ;
		int preLeftTreeEnd = preStart + rootIndex - inStart ;
		int preRightTreeStart = preLeftTreeEnd + 1 ;
		if(inLeftTreeEnd - inStart >= 0){
			root.left = reConstruct(pre, in, preStart+1, preLeftTreeEnd, inStart, inLeftTreeEnd) ;
		}
		if(inEnd - inRightTreeStart >= 0){
			root.right = reConstruct(pre, in, preRightTreeStart, preEnd, inRightTreeStart, inEnd) ;
		}
		
		return root;
	}
	
	public static void main(String[] args) {
		int[] pre = {1,2,4,7,3,5,6,8};
		int[] in = {4,7,2,1,5,3,8,6};
		TreeNode treeNoode= reConstructBinaryTree(pre, in) ;
		System.out.println(treeNoode);
	}
}
